package leetcode;

import java.util.*;

/**
 * Created by Ghost on 2014/12/4 0004.
 */
public class _4Sum {
    private List<List<Integer>> rst = new LinkedList<List<Integer>>();
    public List<List<Integer>> fourSum(int[] num, int target) {
        if (num.length < 4) {
            return rst;
        }
        Arrays.sort(num);
        for (int i = 0; i <= num.length - 4; i++) {
            if (i > 0 && num[i] == num[i - 1])
                continue;
            for (int j = i + 1; j <= num.length - 3; j++) {
                if (j > i + 1 && num[j] == num[j - 1])
                    continue;
                int left = j + 1, right = num.length - 1;
                int t = target - num[i] - num[j];
                while (left < right) {
                    if(left>j+1 && num[left]==num[left-1] && left<right)
                        left++;
                    if(right<num.length-1 && num[right]==num[right+1] && left<right)
                        right--;
                    if(left<right){
                        if(t == (num[left] + num[right])){
                            List<Integer> tmp = new LinkedList<Integer>();
                            tmp.add(num[i]);
                            tmp.add(num[j]);
                            tmp.add(num[left]);
                            tmp.add(num[right]);
                            if(!rst.contains(tmp))
                                rst.add(tmp);
                            left++;
                            right--;
                        }
                        else if(t>(num[left] + num[right])){
                            left++;
                        }
                        else
                            right--;
                    }
                }
            }
        }

        return rst;
    }

    public static void main(String[] args) {
        _4Sum sum = new _4Sum();
        int[] num = {4,-9,-2,-2,-7,9,9,5,10,-10,4,5,2,-4,-2,4,-9,5};
        List<List<Integer>> list = sum.fourSum(num,-13);
        System.out.println(list);
    }
}
